Implement a
balanced binary search tree.
Input. Contains a
description of operations on the tree, with the total number of operations not
exceeding 105. Each line contains one of the following
operations:
·
insert x – insert key x into
the tree. If key x is
already present in the tree, do nothing.
·
delete x – remove key x from
the tree. If key x is not
present in the tree, do nothing.
·
exists x – if key x is
present in the tree, print “true”, otherwise “false”.
All numbers are
integers and do not exceed 109 in absolute value.
Output. Print the
results of all exists operations sequentially,
following the format provided in the example.
|
Sample
input |
Sample
output |
|
insert 2 insert 5 insert 3 exists 2 exists 4 delete 5 |
true false |
data structures - set
Simulate the specified operations using a set data structure.
Declare a set s.
set<int> s;
Read the input data.
while(scanf("%s
%d\n",c,&x) == 2)
{
Insert an element into the set.
if (c[0] == 'i') s.insert(x); else
Remove an element from the set if it exists there.
if (c[0] == 'd') s.erase(x); else
{
Check if an element exists in the set.
if (s.find(x)
!= s.end()) printf("true\n");
else printf("false\n");
}
}
Java
realization
import java.util.*;
public class Main
{
public static void
main(String []args)
{
Scanner con = new Scanner(System.in);
TreeSet<Integer> s = new TreeSet<Integer>();
while(con.hasNext())
{
String c = con.next();
int x = con.nextInt();
if (c.charAt(0) == 'i') s.add(x); else
if (c.charAt(0) == 'd') s.remove(x); else
{
if (s.contains(x))
System.out.println("true");
else
System.out.println("false");
}
}
con.close();
}
}
Python realization
import sys
Declare a set.
s = set()
Read the input data.
for line in sys.stdin:
op, x = line.split()
x
= int(x)
Insert an element into the set.
if op == "insert":
s.add(x)
Remove an element from the set if it exists there.
elif op == "delete":
s.discard(x)
else:
Check if an element exists in the set.
if x in s:
print("true")
else:
print("false")